package com.leecode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * least recently used      LRU
 */
public class Leet146 {
	HashMap map = new HashMap();
	int cap = 0;
	Deque<Map> d = new ArrayDeque();

	public Leet146(int capacity) {
		this.cap = capacity;
	}

	public int get(int key) {
		if(map.containsKey(key)){
			int value = (int) map.get(key);
			//调整ArrayDeque的内部顺序
			//写到这,觉得LinkedHashMap非常合适?!!
//			d.remove()
			return value;
		}else{
			return -1;
		}
	}

	public void put(int key, int value) {
		if (map.size() == cap) {
			Map map = d.removeFirst();
			this.map.remove(map.keySet().iterator().next());
		}
		this.map.put(key, value);
		HashMap hashMap = new HashMap();
		hashMap.put(key,value);
		d.addLast(hashMap);
	}
}
